package com.njupt.Array;

public class BackspaceCompare {

    /**
     * 双指针法
     *
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare(String s, String t) {
        StringBuilder sb = new StringBuilder(s);
        StringBuilder st = new StringBuilder(t);
        int sSlowIndex = 0;
        int tSlowIndex = 0;
        for (int sFastIndex = 0; sFastIndex < sb.length() - 1; sFastIndex++) {
            if (sb.charAt(sFastIndex + 1) != '#') {
//                sb.setCharAt(sSlowIndex,sb.charAt(sFastIndex));
                sSlowIndex++;
            } else {

                sb.deleteCharAt(sSlowIndex);
                if (sSlowIndex > 0) sSlowIndex--;
                sFastIndex--;

            }
        }
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) == '#') {
                sb.deleteCharAt(i);
                i--;
            }
        }
        System.out.println(sb.toString());

        for (int tFastIndex = 0; tFastIndex < st.length() - 1; tFastIndex++) {
            if (st.charAt(tFastIndex + 1) != '#') {
                tSlowIndex++;
            } else {
                st.deleteCharAt(tSlowIndex);
                if (tSlowIndex > 0) tSlowIndex--;
                tFastIndex--;


            }
        }

        for (int i = 0; i < st.length(); i++) {
            if (st.charAt(i) == '#') {
                st.deleteCharAt(i);
                i--;
            }
        }
        System.out.println(st.toString());

        return sb.toString().equals(st.toString());
    }

    /**
     * 重构字符串，每次将需要的字符放入栈中，遇到退格符，就从栈中弹出
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare1(String s, String t) {
        return buildString(s).equals(buildString(t));
    }

    public String buildString(String s) {
        StringBuilder sb = new StringBuilder();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) != '#') {
                sb.append(s.charAt(i));
            } else {
                if (sb.length() > 0) {
                    sb.deleteCharAt(sb.length() - 1);
                }

            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String s = "a##c";
        String t = "#a#c";

        BackspaceCompare test = new BackspaceCompare();
        System.out.println(test.backspaceCompare1(s, t));

    }
}
